package org.aplombh.java.leetcode.all;

import java.util.Deque;
import java.util.LinkedList;

public class _32最长有效括号 {
    public static void main(String[] args) {
        System.out.println(new Solution32_1().longestValidParentheses("()(()"));
    }
}

// 暴力
class Solution32_1 {
    public int longestValidParentheses(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        int ans = 0;

        for (int i = 0, len, flag; i < n; i++) {
            len = 0;
            flag = 0;
            for (int j = i; j < n; j++) {
                if (chars[i] == ')') break;

                if (chars[j] == '(') {
                    flag++;
                }
                if (chars[j] == ')') {
                    if (flag != 0) {
                        flag--;
                        len += 2;
                        if (flag == 0) {
                            ans = Math.max(ans, len);
                        }
                    } else break;
                }
            }
        }
        return ans;
    }
}

// dp
class Solution32_2 {
    public int longestValidParentheses(String s) {
        int ans = 0;
        // 以i位结尾的最长有效括号的长度
        int[] dp = new int[s.length()];
        char[] chars = s.toCharArray();

        for (int i = 1; i < s.length(); i++) {
            if (chars[i] == ')') {
                if (chars[i - 1] == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && chars[i - dp[i - 1] - 1] == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                ans = Math.max(ans, dp[i]);
            }
        }
        return ans;
    }
}

class Solution32_3 {
    public int longestValidParentheses(String s) {
        int maxans = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }
        }
        return maxans;
    }
}